package selected;

import java.util.*;

public class J0819 {
    // 1 两数之和
    public int[] twoSum(int[] nums, int target) {
        // 不能用双指针，因为这里是返回下标而不是值，所以不能排序
        // 使用哈希表，key 存放元素的值，value存放下标进行对应
        int[] ret = new int[2];
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            if(map.containsKey(target - nums[i])){
                ret[0] = i;
                ret[1] = map.get(target - nums[i]);
                return ret;
            }
            map.put(nums[i], i);
        }
        return ret;
    }

    // 2 字母异位词
    public List<List<String>> groupAnagrams(String[] strs) {
        // 字母异位词，重排列之后的字符串一样
        // 使用哈希表，key 为相同的重排列结果，value 为存放所有异位词的list
        Map<String, ArrayList<String>> map = new HashMap<>();
        for(String s : strs){
            char[] c = s.toCharArray();
            Arrays.sort(c);
            String key = new String(c);
            ArrayList<String> list = map.getOrDefault(key, new ArrayList<>());
            list.add(s);
            // 加上之后还要更新回去
            map.put(key, list);
        }
        List<List<String>> ret = new ArrayList<>(map.values());
        return ret;
    }

    // 3 最长连续子序列
    public int longestConsecutive(int[] nums) {
        if(nums.length == 0) return 0;
        Arrays.sort(nums);
        int currentlen = 1;
        int maxlen = 0;
        for(int i = 1; i < nums.length; i++){
            if(nums[i] == nums[i - 1]){
                // 跳过重复元素
                continue;
            } else if(nums[i] == nums[i - 1] + 1){
                // 连续
                currentlen += 1;
            }else {
                // 不连续
                maxlen = Math.max(currentlen, maxlen);
                currentlen = 1;
            }
        }
        return Math.max(currentlen, maxlen);
    }
    // 4 移动 0
    public void moveZeroes(int[] nums) {
        // 0-dest 所有非0元素
        int dest = 0, cur = 0;
        while(cur < nums.length){
            if(nums[cur] == 0){
                cur++;
            } else {
                // 将cur和dest进行互换
                int tmp = nums[cur];
                nums[cur] = nums[dest];
                nums[dest] = tmp;
                dest++; cur++;
            }
        }
    }
    // 5 盛水最多的容器
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1, ret = 0;
        while(left < right){
            int v = (right - left) *
                    Math.min(height[right], height[left]);
            ret = Math.max(v, ret);
            if(height[right] > height[left]) left++;
            else right--;
        }
        return ret;
    }
    // 6 三数之和
    public List<List<Integer>> threeSum(int[] nums) {
        // 双指针，固定其中一个，遍历后边的
        Arrays.sort(nums);
        List<List<Integer>> ret = new ArrayList<>();
        for(int i = 0; i < nums.length; ){
            int left = i + 1, right = nums.length -1, target = -nums[i];
            while(left < right){
                if(nums[left] + nums[right] < target) left++;
                else if(nums[left] + nums[right] > target) right--;
                else {
                    ret.add(new ArrayList<Integer>(Arrays.asList
                            (nums[i], nums[left], nums[right])));
                    left++; right--;
                    while(left < right && nums[left - 1] == nums[left])
                        left++;
                    while(left < right && nums[right + 1] == nums[right])
                        right--;
                }
            }
            i++;
            while(i < nums.length && nums[i - 1] == nums[i]) i++;
        }
        return ret;
    }
    // 7 回文子串
    public int countSubstrings(String s) {
        // 中心展开法
        int ret = 0, n = s.length();
        for(int i = 0; i < n * 2 - 1; i++){
            int left = i / 2, right = i / 2 + i % 2;
            while(left >= 0 && right < n && s.charAt(left) == s.charAt(right)){
                left--;
                right++;
                ret++;
            }
        }
        return ret;
    }
    // 给定字符串再加一个字母能否构成回文串


    public static void main(String[] args) {
        J0819 j0819 = new J0819();
        int[] nums = new int[]{3,2,4};
        int target = 9;
        j0819.twoSum(nums, target);
    }
}
